package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/average-of-levels-in-binary-tree/">二叉树的层平均值(Average of Levels in Binary Tree)</a>
 * <p>给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10^-5 以内的答案可以被接受。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [3,9,20,null,null,15,7]
 *      输出：[3.00000,14.50000,11.00000]
 *      解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
 *      因此返回 [3, 14.5, 11] 。
 *
 * 示例 2:
 *      输入：root = [3,9,20,15,7]
 *      输出：[3.00000,14.50000,11.00000]
 * </pre>
 * </p>
 * <p>
 * <b>提示:</b>
 * <ul>
 *     <li>树中节点数量在 [1, 10^4] 范围内</li>
 *     <li>-2^31 <= Node.val <= 2^31 - 1</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/18 17:59
 */
public class LC0637AverageOfLevelsInBinaryTree_S {

    static class Solution {
        public List<Double> averageOfLevels(TreeNode root) {
            List<Double> retList = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int currLevelNodeNum = queue.size();
                double sum = 0;
                for (int i = 0; i < currLevelNodeNum; i++) {
                    TreeNode currNode = queue.poll();
                    sum += currNode.val;
                    if (currNode.left != null) {
                        queue.offer(currNode.left);
                    }
                    if (currNode.right != null) {
                        queue.offer(currNode.right);
                    }
                }
                retList.add(sum / currLevelNodeNum);
            }
            return retList;
        }
    }
}
